#include <iostream>
#include <deque>
#include <string.h>

using namespace std;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

struct cell {
	int x, y, k;
	cell ()
	{
		x = 0;
		y = 0;
		k = 0;
	}
	cell (int xx, int yy, int kk)
	{
		x = xx;
		y = yy;
		k = kk;
	}
};
int d[21][20][20];
int a[20][20];
int m, n, k;

bool inside(cell u)
{
	return (0 <= u.x && u.x < m && 0 <= u.y && u.y <= n);
}

int main()
{
	deque<cell> q;

	int ntest;
	cin >> ntest;
	while (0 < ntest--)
	{
		cin >> m >> n >> k;
		for (int i = 0; i < m; i++) 
			for (int j = 0; j < n; j++) cin >> a[i][j];

		memset(d, -1, sizeof(d));
		
		d[0][0][0] = 0;
		cell start(0, 0, 0);
		q.push_back(start);

		while (!q.empty())
		{
			cell u = q.front();
			q.pop_front();

//			cout << u.x << " " << u.y << " " << u.k << endl;
			for (int i = 0; i < 4; i++) 
			{
				cell v;
				v.x = u.x + dx[i];
				v.y = u.y + dy[i];
				if (a[v.x][v.y] == 0) v.k = 0;
				else v.k = u.k+1;
				
				if (v.k > k) continue;

				if (inside(v) && (d[v.k][v.x][v.y] == -1 || (d[u.k][u.x][u.y] + 1 < d[v.k][v.x][v.y])))
				{
					d[v.k][v.x][v.y] = d[u.k][u.x][u.y] + 1;
					q.push_back(v);
//					cout << "--> " << v.x << " " << v.y << " " << v.k << " " << d[v.k][v.x][v.y] << endl;
				}
			}
		}
		cout << d[0][m-1][n-1] << endl;
	}
	return 0;
}
